package company.qianxing_F;

import java.util.Arrays;
import java.util.Scanner;

// 完全背包问题（可以选择多次）
// 可以选择用递归来做，估计会超时
public class Q1B {

//    测试用例1
//    100
//    5
//    77 92
//    22 22
//    29 36
//    50 46
//    99 90
//    结果
//    114
//
//    测试用例2
//    200
//    8
//    79 83
//    58 81
//    86 54
//    110 150
//    62 52
//    45 48
//    68 62
//    30 22

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt();
        int len = sc.nextInt();
        //价格
        int[] w = new int[len + 1];
        //价值
        int[] v = new int[len + 1];
        w[0] = 0;
        v[0] = 0;
        for (int i = 1; i <= len; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        // 第几种商品 花了多少钱 值为最大价值
        int[][] dp = new int[len + 1][money + 1];
        // 第i种商品
        for (int i = 1; i <= len; i++) {
            //花多少钱 可以选取多次所以从1开始
            for (int j = 1; j <= money; j++) {
                //dp[i][j] 最大价值
                if (w[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else {
                    // k表示选取几个物品
                    int max = 0;
                    for (int k = 0;k * w[i] <= j; k++) {
                        max = Math.max(max, dp[i - 1][j - w[i] * k] + v[i] * k);
                    }
                    dp[i][j] = max;
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println(dp[len][money]);
    }

    //0-1背包问题 这个东西要么选，要么不选
    public void bag(int[] volume, int[] value, int bag) {
        int n = volume.length;
        int[][] dp = new int[n + 1][bag + 1];
        for (int i = 1; i <= n; i++) {
            //只能选取一次 所以选择j>=v[i] 选或者不选
            for (int j = 1; j <= bag; j++) {
                if (volume[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - volume[i - 1]] + value[i - 1]);
            }
        }
    }

}
